package search

// 简单的二分查找（假设数组不重复）
func (this *Search) SimpleBinarySearch(arr []int, value int) int {

	low, high := 0, len(arr)-1

	for low <= high {
		mid := low + ((high - low) >> 1)

		if value < arr[mid] {
			high = mid - 1
		} else if value > arr[mid] {
			low = mid + 1
		} else {
			return mid
		}
	}

	return -1
}

// 查找第一个等于查找值的数组下标
func (this *Search) FindFirstEqByBinarySearch(arr []int, value int) int {
	// 起终点
	low, high := 0, len(arr)-1

	for low <= high {
		mid := low + ((high - low) >> 1)

		if value < arr[mid] {
			high = mid - 1
		} else if value > arr[mid] {
			low = mid + 1
		} else {
			if mid == 0 || arr[mid-1] != arr[mid] {
				return mid
			}
			high = mid - 1
		}
	}

	return -1
}

// 查找数组中等于查找值得最后一个元素下标
func (this *Search) FindLastEqByBinarySearch(arr []int, value int) int {

	// 查询的起始坐标
	low, high := 0, len(arr)-1

	for low <= high {
		mid := low + ((high - low) >> 1)

		if value < arr[mid] {
			high = mid - 1
		} else if value > arr[mid] {
			low = mid + 1
		} else {
			if mid == len(arr)-1 || arr[mid+1] != value {
				return mid
			}
			low = mid + 1
		}
	}

	return -1
}

// 查找第一个大于等于查找值的数组元素下标
func (this *Search) FindFirstEgtByBinarySearch(arr []int, value int) int {
	// 数组起始
	low, high := 0, len(arr)-1

	for low <= high {
		mid := low + ((high - low) >> 1)
		if value > arr[mid] {
			low = mid + 1
		} else {
			if mid == 0 || arr[mid-1] < value {
				return mid
			}
			high = mid - 1
		}
	}

	return -1
}

// 查找最后一个小于等于给定值的元素下标
func (this *Search) FindLastEltByBinarySearch(arr []int, value int) int {

	low, high := 0, len(arr)-1

	for low <= high {
		mid := low + ((high - low) >> 1)
		if value < arr[mid] {
			high = mid - 1
		} else {
			if mid == len(arr)-1 || arr[mid+1] > value {
				return mid
			}
			low = mid + 1
		}
	}

	return -1
}
